package lib

//link to 
func init() {
	Probs = append(Probs, Problem{
		Num:         518,
		Discription: "给定硬币种类凑成指定值的组合数",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"完全背包": 1,
			"空间降维": 1,
		},
	})
}

func Change(amount int, coins []int) int {
	if amount == 0 {
		return 1
	}

	//dp[i][j]表示用coins[:i+1]中的硬币种类凑成值为k的组合数
	dp := make([][]int, len(coins)+1)
	for i := range dp {
		dp[i] = make([]int, amount+1)
	}

	//大循环先遍历coins
	for i := 1; i <= len(coins); i++ {
		coin := coins[i-1]
		for j := 1; j <= amount; j++ {
			if coin == j {
				dp[i][j] = dp[i-1][j] + 1
			} else if coin > j {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] + dp[i][j-coin]
			}
		}
	}

	return dp[len(coins)][amount]
}